package 第9场小白入门赛;
import java.io.*;
import java.util.*;
public class 无理数位数查询 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int n,m;
		int t = Integer.parseInt(br.readLine());
		StringBuilder stb;
		int i;
		while(t-- > 0) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			stb = new StringBuilder();
			i = 0;
			while(true) {
				i++;
				stb.append(Integer.toString(i, m)) ;
				if(stb.length() >= n) {
					break;
				}	
			}
			
			bw.write(stb.substring(n-1, n));
			if(t!=0) {
				bw.newLine();			
			}
		}
		bw.flush();	
	}
}
